#include <stddef.h>
#include <stdlib.h>     // calloc(), free()
#include <assert.h>
#include <string>
#include <cstring>
#include "hashtable.h"
#include "common.h"

/**
 * @brief 初始化哈希表，n必须是2的幂
 * @param htab 哈希表指针
 * @param n 哈希表大小
 */
static void h_init(HTab *htab, size_t n) 
{
    assert(n > 0 && ((n - 1) & n) == 0);
    htab->tab = (HNode **)calloc(n, sizeof(HNode *));
    htab->mask = n - 1;
    htab->size = 0;
}

/**
 * @brief 向哈希表中插入节点
 * @param htab 哈希表指针
 * @param node 要插入的节点
 */
static void h_insert(HTab *htab, HNode *node) 
{
    size_t pos = node->hcode & htab->mask;
    HNode *next = htab->tab[pos];
    node->next = next;
    htab->tab[pos] = node;
    htab->size++;
}

/**
 * @brief 哈希表查找子程序
 * 注意返回值：返回拥有目标节点的父指针的地址，可用于删除目标节点
 * @param htab 哈希表指针
 * @param key 查找的键
 * @param eq 比较函数
 * @return 指向目标节点指针的指针
 */
static HNode **h_lookup(HTab *htab, HNode *key, bool (*eq)(HNode *, HNode *)) 
{
    if (!htab->tab) 
    {
        return NULL;
    }

    size_t pos = key->hcode & htab->mask;
    HNode **from = &htab->tab[pos];     // 指向目标的传入指针
    for (HNode *cur = nullptr; (cur = *from) != NULL; from = &cur->next) 
    {
        if (cur->hcode == key->hcode && eq(cur, key)) 
        {
            return from;                // 可能是节点，可能是槽位
        }
    }
    return NULL;
}

/**
 * @brief 从链表中移除节点
 * @param htab 哈希表指针
 * @param from 指向目标节点指针的指针
 * @return 被移除的节点
 */
static HNode *h_detach(HTab *htab, HNode **from) 
{
    HNode *node = *from;    // 目标节点
    *from = node->next;     // 更新指向目标的传入指针
    htab->size--;
    return node;
}

const size_t k_rehashing_work = 128;    // 常量工作量

/**
 * @brief 帮助进行rehash操作
 * @param hmap 哈希映射指针
 */
static void hm_help_rehashing(HMap *hmap) 
{
    size_t nwork = 0;
    while (nwork < k_rehashing_work && hmap->older.size > 0) 
    {
        // 找到一个非空槽位
        HNode **from = &hmap->older.tab[hmap->migrate_pos];
        if (!*from) 
        {
            hmap->migrate_pos++;
            continue;   // 空槽位
        }
        // 将第一个链表项移动到新表
        h_insert(&hmap->newer, h_detach(&hmap->older, from));
        nwork++;
    }

    // 如果完成则丢弃旧表
    if (hmap->older.size == 0 && hmap->older.tab) 
    {
        free(hmap->older.tab);
        hmap->older = HTab{};
    }
}

/**
 * @brief 触发rehash操作
 * @param hmap 哈希映射指针
 */
static void hm_trigger_rehashing(HMap *hmap) 
{
    assert(hmap->older.tab == NULL);
    // (newer, older) <- (new_table, newer)
    hmap->older = hmap->newer;
    h_init(&hmap->newer, (hmap->newer.mask + 1) * 2);
    hmap->migrate_pos = 0;
}

HNode *hm_lookup(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) 
{
    hm_help_rehashing(hmap);
    HNode **from = h_lookup(&hmap->newer, key, eq);
    if (!from) 
    {
        from = h_lookup(&hmap->older, key, eq);
    }
    return from ? *from : NULL;
}

const size_t k_max_load_factor = 8;

void hm_insert(HMap *hmap, HNode *node) 
{
    if (!hmap->newer.tab) 
    {
        h_init(&hmap->newer, 4);    // 如果为空则初始化
    }
    h_insert(&hmap->newer, node);   // 总是插入到新表

    if (!hmap->older.tab) 
    {
        // 检查是否需要rehash
        size_t threshold = (hmap->newer.mask + 1) * k_max_load_factor;
        if (hmap->newer.size >= threshold) 
        {
            hm_trigger_rehashing(hmap);
        }
    }
    hm_help_rehashing(hmap);        // 迁移一些键
}

HNode *hm_delete(HMap *hmap, HNode *key, bool (*eq)(HNode *, HNode *)) 
{
    hm_help_rehashing(hmap);
    
    // 先在新表中查找
    HNode **from = h_lookup(&hmap->newer, key, eq);
    if (from) 
    {
        return h_detach(&hmap->newer, from);
    }
    
    // 再在旧表中查找
    if (hmap->older.tab) 
    {
        from = h_lookup(&hmap->older, key, eq);
        if (from) 
        {
            return h_detach(&hmap->older, from);
        }
    }
    
    return NULL;
}

void hm_clear(HMap *hmap) 
{
    free(hmap->newer.tab);
    free(hmap->older.tab);
    *hmap = HMap{};
}

size_t hm_size(HMap *hmap) 
{
    return hmap->newer.size + hmap->older.size;
}

/**
 * @brief 遍历单个哈希表
 * @param htab 哈希表指针
 * @param f 回调函数
 * @param arg 传递给回调函数的参数
 * @return 如果所有回调都返回true则返回true
 */
static bool h_foreach(HTab *htab, bool (*f)(HNode *, void *), void *arg) 
{
    for (size_t i = 0; htab->mask != 0 && i <= htab->mask; i++) 
    {
        for (HNode *node = htab->tab[i]; node != NULL; node = node->next) 
        {
            if (!f(node, arg)) 
            {
                return false;
            }
        }
    }
    return true;
}

void hm_foreach(HMap *hmap, bool (*f)(HNode *, void *), void *arg) 
{
    h_foreach(&hmap->newer, f, arg) && h_foreach(&hmap->older, f, arg);
}

void hm_init(HMap *hmap) 
{
    *hmap = HMap{};
}

/**
 * @brief 扫描单个哈希表
 * @param htab 哈希表指针
 * @param from 开始扫描的节点指针的指针
 * @return 下一个节点指针，如果没有更多节点返回NULL
 */
static HNode *h_scan(HTab *htab, HNode **from) 
{
    if (!htab->tab) 
    {
        return NULL;
    }
    
    HNode *node = *from;
    if (node) 
    {
        // 继续当前链表
        *from = node->next;
        if (*from) 
        {
            return *from;
        }
        // 移动到下一个槽位
        size_t pos = (node->hcode & htab->mask) + 1;
        for (size_t i = pos; i <= htab->mask; i++) 
        {
            if (htab->tab[i]) 
            {
                *from = htab->tab[i];
                return *from;
            }
        }
    } 
    else 
    {
        // 从头开始扫描
        for (size_t i = 0; i <= htab->mask; i ++ ) 
        {
            if (htab->tab[i]) 
            {
                *from = htab->tab[i];
                return *from;
            }
        }
    }
    
    *from = NULL;
    return NULL;
}

HNode *hm_scan(HMap *hmap, HNode **from) 
{
    hm_help_rehashing(hmap);
    
    // 首先扫描新表
    HNode *node = h_scan(&hmap->newer, from);
    if (node) 
    {
        return node;
    }
    
    // 然后扫描旧表
    return h_scan(&hmap->older, from);
}

/**
 * @brief 按键查找的辅助结构
 */
struct HKey 
{
    HNode node;
    const uint8_t *key = NULL;
    size_t len = 0;
};

/**
 * @brief 哈希表键比较函数
 * @param node 哈希表节点
 * @param key 查找键
 * @return 如果相等返回true
 */
static bool hkey_eq(HNode *node, HNode *key) 
{
    struct Entry 
    {
        HNode node;
        std::string key;
        std::string val;
        uint32_t type;
        void *zset;
        size_t heap_idx;
        uint64_t expire_at;
    };
    
    struct HKey 
    {
        HNode node;
        const uint8_t *key;
        size_t len;
    };
    
    Entry *ent = container_of(node, Entry, node);
    HKey *hkey = container_of(key, HKey, node);
    if (ent->key.size() != hkey->len) 
    {
        return false;
    }
    return 0 == memcmp(ent->key.data(), hkey->key, hkey->len);
}

HNode *hm_lookup(HMap *hmap, const uint8_t *key, size_t len) 
{
    HKey hkey;
    hkey.node.hcode = str_hash(key, len);
    hkey.key = key;
    hkey.len = len;
    return hm_lookup(hmap, &hkey.node, &hkey_eq);
}

HNode *hm_pop(HMap *hmap, const uint8_t *key, size_t len) 
{
    HKey hkey;
    hkey.node.hcode = str_hash(key, len);
    hkey.key = key;
    hkey.len = len;
    return hm_delete(hmap, &hkey.node, &hkey_eq);
} 